{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Length of a Concatenated String with Unique Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #串联字符串的最大长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串数组 <code>arr</code>，字符串 <code>s</code> 是将 <code>arr</code>&nbsp;的含有 <strong>不同字母</strong> 的&nbsp;<strong>子序列</strong> 字符串 <strong>连接</strong> 所得的字符串。</p>\n",
    "\n",
    "<p>请返回所有可行解 <code>s</code> 中最长长度。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [\"un\",\"iq\",\"ue\"]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>所有可能的串联组合是：\n",
    "- \"\"\n",
    "- \"un\"\n",
    "- \"iq\"\n",
    "- \"ue\"\n",
    "- \"uniq\" (\"un\" + \"iq\")\n",
    "- \"ique\" (\"iq\" + \"ue\")\n",
    "最大长度为 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [\"cha\",\"r\",\"act\",\"ers\"]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>可能的解答有 \"chaers\" 和 \"acters\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [\"abcdefghijklmnopqrstuvwxyz\"]\n",
    "<strong>输出：</strong>26\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 16</code></li>\n",
    "\t<li><code>1 &lt;= arr[i].length &lt;= 26</code></li>\n",
    "\t<li><code>arr[i]</code>&nbsp;中只含有小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-length-of-a-concatenated-string-with-unique-characters](https://leetcode.cn/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-length-of-a-concatenated-string-with-unique-characters](https://leetcode.cn/problems/maximum-length-of-a-concatenated-string-with-unique-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"un\",\"iq\",\"ue\"]', '[\"cha\",\"r\",\"act\",\"ers\"]', '[\"abcdefghijklmnopqrstuvwxyz\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        nums = {}\n",
    "        n = len(arrays)\n",
    "\n",
    "        que = [ [arrays[i][0], arrays[i][-1]] for i in range(n)]\n",
    "\n",
    "        heapq.heapify(que)\n",
    "        maxLength = 0\n",
    "        minNum, maxNum = heapq.heappop(que)\n",
    "        maxLength = float(\"-inf\")\n",
    "        while que:\n",
    "            min_, max_ = heapq.heappop(que)\n",
    "\n",
    "            maxLength = max(abs(min_ - maxNum), abs(minNum - max_), maxLength)\n",
    "            maxNum = max(max_, maxNum)\n",
    "\n",
    "        return maxLength\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        nums = {}\n",
    "        n = len(arrays)\n",
    "\n",
    "        que = [ [arrays[i][0], arrays[i][-1]] for i in range(n)]\n",
    "\n",
    "        heapq.heapify(que)\n",
    "        maxLength = 0\n",
    "        minNum, maxNum = heapq.heappop(que)\n",
    "        maxLength = float(\"-inf\")\n",
    "        while que:\n",
    "            min_, max_ = heapq.heappop(que)\n",
    "\n",
    "            maxLength = max(abs(min_ - maxNum), abs(minNum - max_), maxLength)\n",
    "            maxNum = max(max_, maxNum)\n",
    "\n",
    "        return maxLength\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        arr = [i for i in arr if len(set(i)) == len(i)]\n",
    "        n = len(arr)\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(strs, i):\n",
    "            nonlocal ret\n",
    "            if i == n:\n",
    "                ret = max(ret, len(strs))\n",
    "                return\n",
    "            if not set(arr[i]) & set(strs):\n",
    "                dfs(strs + arr[i], i + 1)\n",
    "            dfs(strs, i + 1)\n",
    "\n",
    "        dfs('', 0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        #就判断+排除就好了\n",
    "        def f(i, exclude):\n",
    "\n",
    "            if i == len(arr):\n",
    "                return 0\n",
    "            r1 = 0\n",
    "            if len(set(arr[i])) == len(arr[i]) and all(a not in exclude for a in arr[i]):\n",
    "                for a in arr[i]:\n",
    "                    exclude.add(a)\n",
    "                r1 = len(arr[i]) + f(i + 1, exclude)\n",
    "                for a in arr[i]:\n",
    "                    exclude.remove(a)\n",
    "            \n",
    "            r2 = f(i + 1, exclude)\n",
    "            return max(r1, r2)\n",
    "        \n",
    "        return f(0, set())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        #就判断+排除就好了\n",
    "        def f(i, exclude):\n",
    "\n",
    "            if i == len(arr):\n",
    "                return 0\n",
    "            r1 = 0\n",
    "            if len(set(arr[i])) == len(arr[i]) and all(a not in exclude for a in arr[i]):\n",
    "                for a in arr[i]:\n",
    "                    exclude.add(a)\n",
    "                r1 = len(arr[i]) + f(i + 1, exclude)\n",
    "                for a in arr[i]:\n",
    "                    exclude.remove(a)\n",
    "            \n",
    "            r2 = f(i + 1, exclude)\n",
    "            return max(r1, r2)\n",
    "        \n",
    "        return f(0, set())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        #就判断+排除就好了\n",
    "        def f(i, exclude):\n",
    "\n",
    "            if i == len(arr):\n",
    "                return 0\n",
    "            r1 = 0\n",
    "            if len(set(arr[i])) == len(arr[i]) and all(a not in exclude for a in arr[i]):\n",
    "                for a in arr[i]:\n",
    "                    exclude.add(a)\n",
    "                r1 = len(arr[i]) + f(i + 1, exclude)\n",
    "                for a in arr[i]:\n",
    "                    exclude.remove(a)\n",
    "            \n",
    "            r2 = f(i + 1, exclude)\n",
    "            return max(r1, r2)\n",
    "        \n",
    "        return f(0, set())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # 回溯算法(考虑是否有重复字符)\n",
    "        result = 0\n",
    "        temp = []\n",
    "\n",
    "        # 检查是否满足字符唯一的条件\n",
    "        def can_add(current, temp):\n",
    "            concat_str = ''.join(temp)\n",
    "            for c in current:\n",
    "                if c in concat_str:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 检查字符串本身有没有重复的字符\n",
    "        def is_distinct(current):\n",
    "            return len(set(current)) == len(current)\n",
    "\n",
    "        def backtrace(start, temp, arr): \n",
    "\n",
    "            nonlocal result \n",
    "            result = max(result, len(''.join(temp)))\n",
    "\n",
    "\n",
    "            for i in range(start, len(arr)):\n",
    "                \n",
    "                # 这里可以控制谁要加进来, 谁可以继续回溯和pop\n",
    "                if can_add(arr[i], temp) and is_distinct(arr[i]):\n",
    "                    temp.append(arr[i])\n",
    "                    backtrace(i+1, temp, arr)\n",
    "                    temp.pop(-1)\n",
    "\n",
    "        backtrace(0, temp, arr)\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def check(self, str1):\n",
    "        dic = defaultdict(int)\n",
    "        for x in str1:\n",
    "            dic[x] += 1\n",
    "            if dic[x] > 1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        def dfs(i, path:str):\n",
    "            nonlocal n, res\n",
    "            if i >= n:\n",
    "                print(len(path))\n",
    "                res = max(res, len(path))\n",
    "                return\n",
    "\n",
    "            flag = self.check(arr[i])\n",
    "            if not flag:\n",
    "                for s in arr[i]:\n",
    "                    if s in path:\n",
    "                        flag = True\n",
    "                        break\n",
    "            if flag:\n",
    "                dfs(i+1, path)\n",
    "            else:\n",
    "                dfs(i+1, path)\n",
    "                dfs(i+1, path+arr[i])\n",
    "\n",
    "        dfs(0, \"\")\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        result = []\n",
    "        self.backtracking(arr, '', 0, result)\n",
    "        return max(result)\n",
    "\n",
    "    def backtracking(self, arr, path, startint, result):\n",
    "        if len(path) != len(set(path)):\n",
    "            return\n",
    "        else:\n",
    "            result.append(len(path))\n",
    "        for i in range(startint, len(arr)):\n",
    "            path += arr[i]\n",
    "            self.backtracking(arr, path, i + 1, result)\n",
    "            path = path[:len(path) - len(arr[i])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr):#集合dp剪枝测试\n",
    "        dp=[]\n",
    "        restLen=[0,len(arr[-1])]\n",
    "        for i in range(len(arr)-2,0,-1):\n",
    "            restLen.append(restLen[-1]+len(arr[i]))\n",
    "        restLen.reverse()\n",
    "        maxLen=0\n",
    "        for i in range(len(arr)):\n",
    "            si=set(list(arr[i]))\n",
    "            if len(si)==len(arr[i]):\n",
    "                for j in range(len(dp)-1,-1,-1):\n",
    "                    if dp[j][0]&si==set() and dp[j][1]+len(arr[i])+restLen[i]>=maxLen:\n",
    "                        dp.append([dp[j][0]|si,dp[j][1]+len(arr[i])])\n",
    "                        maxLen=max(maxLen,dp[j][1]+len(arr[i]))\n",
    "                dp.append([si,len(arr[i])])\n",
    "                maxLen=max(maxLen,len(arr[i]))\n",
    "        return max([i[1] for i in dp]) if len(dp)>0 else 0\n",
    "    def maxLength2(self, arr):#集合，dp，148 ms，37.87%，59.6 MB，5.32%\n",
    "        dp=[]\n",
    "        for i in arr:\n",
    "            si=set(list(i))\n",
    "            if len(si)==len(i):\n",
    "                for j in range(len(dp)-1,-1,-1):\n",
    "                    if dp[j][0]&si==set():\n",
    "                        dp.append([dp[j][0]|si,dp[j][1]+len(i)])\n",
    "                dp.append([si,len(i)])\n",
    "        return max([i[1] for i in dp]) if len(dp)>0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        \n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            \n",
    "            for ch in s:\n",
    "                idx = ord(ch)-ord('a')\n",
    "                if (mask>>idx)&1:\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask = mask | 1<<idx\n",
    "            if mask == 0:\n",
    "                continue\n",
    "                \n",
    "            for i in range(len(masks)):\n",
    "                current = masks[i]\n",
    "                if current & mask == 0:\n",
    "                    masks.append(mask|current)\n",
    "                    ans = max(ans, bin(mask|current).count('1'))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if ((mask >> idx) & 1):   # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx   # 将 ch 加入 mask 中\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            n = len(masks)\n",
    "            for i in range(n):\n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, bin(m | mask).count(\"1\"))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if ((mask >> idx) & 1):   # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx   # 将 ch 加入 mask 中\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            n = len(masks)\n",
    "            for i in range(n):\n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, bin(m | mask).count(\"1\"))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if ((mask >> idx) & 1):   # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx   # 将 ch 加入 mask 中\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            for m in masks:\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, bin(m | mask).count(\"1\"))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if ((mask >> idx) & 1):   # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx   # 将 ch 加入 mask 中\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            n = len(masks)\n",
    "            for i in range(n):\n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, bin(m | mask).count(\"1\"))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for c in s:\n",
    "                i = ord(c) - ord('a')\n",
    "                if mask >> i & 1:\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << i\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            for m in masks:\n",
    "                if m & mask == 0:\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, (m | mask).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        masks = [0]\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if ((mask >> idx) & 1):   # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx   # 将 ch 加入 mask 中\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            n = len(masks)\n",
    "            for i in range(n):\n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "                    ans = max(ans, bin(m | mask).count(\"1\"))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        masks = [0] #0必须有\n",
    "        ans = 0\n",
    "        for s in arr:\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                idx = ord(ch) - ord('a')\n",
    "                if (mask >> idx) & 1:\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1 << idx\n",
    "            if mask == 0:\n",
    "                continue\n",
    "        \n",
    "            n = len(masks)\n",
    "            for i in range(n):\n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:   # m 和 mask 无公共元素\n",
    "                    masks.append(m | mask)\n",
    "        return max([bin(mask).count('1') for mask in masks])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        bin_arr=[]\n",
    "\n",
    "        for s in arr:\n",
    "            tmp=0\n",
    "            for ch in s:\n",
    "                index=ord(ch)-ord('a')\n",
    "                if (tmp>>index)&1==1:\n",
    "                    tmp=0\n",
    "                    break\n",
    "                tmp |= (1<<index)\n",
    "            if tmp>0:\n",
    "                bin_arr.append(tmp)\n",
    "        \n",
    "        n=len(bin_arr)\n",
    "        res=[]\n",
    "        def backtrace(index,cnt):\n",
    "            res.append(cnt)\n",
    "            if index==n:\n",
    "                return \n",
    "            else:\n",
    "                for i in range(index,n):\n",
    "                    if (cnt & bin_arr[i])==0:\n",
    "                        backtrace(i+1,cnt|bin_arr[i])\n",
    "        backtrace(0,0)\n",
    "\n",
    "        return max([bin(s).count('1') for s in res])\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isDifferent(tmp):\n",
    "    list = [_ for _ in tmp]\n",
    "    list_to_set = set(list)\n",
    "    if len(list) == len(list_to_set):\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "\n",
    "def getLength(result_all):\n",
    "    list = [len(s) for s in result_all]\n",
    "    return max(list) if list != [] else 0\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxLength(self, arr):\n",
    "\n",
    "        result_all = []\n",
    "\n",
    "        def dfs(index, tmp):\n",
    "            # 列表已经遍历完，返回\n",
    "            if index == len(arr):\n",
    "                return\n",
    "\n",
    "            # 遍历当前列表\n",
    "            for i in range(index, len(arr)):\n",
    "                init_str = tmp\n",
    "                tmp += arr[i]\n",
    "                # 判断是否重复，有重复，返回\n",
    "                if not isDifferent(tmp):\n",
    "                    tmp = init_str\n",
    "                    continue\n",
    "                result_all.append(tmp)\n",
    "                dfs(i + 1, tmp)\n",
    "                tmp = init_str\n",
    "\n",
    "            return\n",
    "\n",
    "        dfs(0, \"\")\n",
    "        return getLength(result_all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans=0\n",
    "        masks=[0]\n",
    "        for s in arr:\n",
    "            mask=0\n",
    "            for ch in s:\n",
    "                idx=ord(ch)-ord('a')\n",
    "                if (mask>>idx)&1:\n",
    "                    mask=0\n",
    "                    break\n",
    "                mask|=1<<idx\n",
    "            if mask==0:\n",
    "                continue\n",
    "            n=len(masks)\n",
    "            for i in range(n):\n",
    "                m=masks[i]\n",
    "                if m&mask==0:\n",
    "                    masks.append(m|mask)\n",
    "                    ans=max(ans,bin(m|mask).count(\"1\"))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "\n",
    "        ans = 0 \n",
    "        masks = [0]\n",
    "\n",
    "        for s in arr: \n",
    "            mask = 0 \n",
    "\n",
    "            for ch in s: \n",
    "                idx = ord(ch) - ord('a')\n",
    "\n",
    "                if ((mask >> idx) & 1): \n",
    "                    mask = 0 \n",
    "                    break \n",
    "                \n",
    "                mask |= 1 << idx\n",
    "                \n",
    "            if mask == 0: \n",
    "                continue \n",
    "        \n",
    "            n = len(masks)\n",
    "            for i in range(n): \n",
    "                m = masks[i]\n",
    "                if (m & mask) == 0:\n",
    "                    masks.append(m | mask)\n",
    "                \n",
    "                    ans = max(ans, bin(m |mask).count('1'))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def mutate(s):\n",
    "            x = 0\n",
    "            for c in s:\n",
    "                if (1<<(ord(c)-ord('a'))) & x:\n",
    "                    return 0\n",
    "                else:\n",
    "                    x |= (1<<(ord(c)-ord('a')))\n",
    "            return x\n",
    "        arr = map(mutate, arr)\n",
    "        cur = [0]\n",
    "        ans = 0\n",
    "        def ct_ones(i):\n",
    "            ct = 0\n",
    "            while i:\n",
    "                ct += 1\n",
    "                i &= (i - 1)\n",
    "            return ct\n",
    "        \n",
    "        for x in arr:\n",
    "            temp = cur[:]\n",
    "            for y in temp:\n",
    "                if x & y == 0:\n",
    "                    cur.append(x | y)\n",
    "                    ans = max(ans, ct_ones(x | y))\n",
    "                    if ans == 26:\n",
    "                        return 26\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def mutate(s):\n",
    "            x = 0\n",
    "            for c in s:\n",
    "                if (1<<(ord(c)-ord('a'))) & x:\n",
    "                    return 0\n",
    "                else:\n",
    "                    x |= (1<<(ord(c)-ord('a')))\n",
    "            return x\n",
    "        arr = map(mutate, arr)\n",
    "        cur = [0]\n",
    "        ans = 0\n",
    "        def ct_ones(i):\n",
    "            ct = 0\n",
    "            while i:\n",
    "                ct += 1\n",
    "                i &= (i - 1)\n",
    "            return ct\n",
    "        \n",
    "        for x in arr:\n",
    "            temp = cur[:]\n",
    "            for y in temp:\n",
    "                if x & y == 0:\n",
    "                    cur.append(x | y)\n",
    "                    ans = max(ans, ct_ones(x | y))\n",
    "                    if ans == 26:\n",
    "                        return 26\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        n = len(arr)\n",
    "        arr_bit = []\n",
    "        for idx in range(n):\n",
    "            tmp = 0\n",
    "            for char in arr[idx]:\n",
    "                if tmp & 1<<(ord(char)-ord(\"a\")) ==1<<(ord(char)-ord(\"a\")):\n",
    "                    tmp=0\n",
    "                    break\n",
    "                else:\n",
    "                    tmp= 1<<(ord(char)-ord(\"a\")) | tmp\n",
    "            if tmp!=0:\n",
    "                arr_bit.append(tmp)\n",
    "        def cal1(x: int) -> int:\n",
    "            res = 0\n",
    "            while x!=0:\n",
    "                res += x&1\n",
    "                x = x>>1\n",
    "            return res\n",
    "        arr_len = [cal1(x) for x in arr_bit]\n",
    "        cur = 0\n",
    "        q = collections.deque()\n",
    "        q.append((0,0))\n",
    "        self.res = 0\n",
    "        # print(arr_bit)\n",
    "        visited = set()\n",
    "        def dfs(curword, curlength):\n",
    "            # print(curword)\n",
    "            if curword in visited:\n",
    "                return\n",
    "            visited.add(curword)\n",
    "            if curlength > self.res:\n",
    "                self.res = curlength\n",
    "            for word,length in zip(arr_bit,arr_len):\n",
    "                if (word+curword) not in visited and  word | curword == word+curword:\n",
    "                    \n",
    "                    dfs(word+curword,curlength+length)\n",
    "        dfs(0,0)\n",
    "        return self.res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools as it\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        comb = ['']\n",
    "        ans =0\n",
    "        \n",
    "        for s in arr:\n",
    "            add = []\n",
    "            for c in comb:\n",
    "                t = s+c\n",
    "                if len(t) == len(set(t)):\n",
    "                    add.append(t)\n",
    "                    ans = max(len(t),ans)\n",
    "            comb.extend(add)\n",
    "        return ans\n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        collect = ['']\n",
    "        ans = 0\n",
    "        for s in arr:\n",
    "            for c in collect:\n",
    "                t = c+s\n",
    "                if len(t)==len(set(t)):\n",
    "                    collect.append(t)\n",
    "                    ans=max(len(t),ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        s = len(arr)\n",
    "        masks =[0]\n",
    "        maxx = 0\n",
    "        for string in arr:\n",
    "            mask = 0\n",
    "            for char in string:\n",
    "                idx = ord(char)-ord(\"0\")\n",
    "                if ((mask>> idx) & 1):\n",
    "                    mask = 0\n",
    "                    break\n",
    "                mask |= 1<<idx\n",
    "            if mask == 0:\n",
    "                continue\n",
    "            \n",
    "            n = len(masks)\n",
    "            for m in masks:\n",
    "                if (m&mask) == 0:\n",
    "                    masks.append(mask | m)\n",
    "                    maxx = max(maxx,bin(mask|m).count(\"1\"))\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        res = 0\n",
    "        q = ['']\n",
    "        for s in arr:\n",
    "            tmp = []\n",
    "            for x in q:\n",
    "                contents = s + x\n",
    "                if len(contents) == len(set(contents)):\n",
    "                    tmp.append(contents)\n",
    "                    res = max(res, len(contents))\n",
    "            q.extend(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def validStr(string):\n",
    "            return len(set(string)) == len(string)\n",
    "        \n",
    "        dp = []\n",
    "        for s in arr:\n",
    "            if not validStr(s):\n",
    "                continue\n",
    "            for s_ in list(dp):\n",
    "                if validStr(s_ + s):\n",
    "                    dp.append(s_ + s)\n",
    "            dp.append(s)\n",
    "        return len(max(dp, key=len)) if dp else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: list[str]) -> int:\n",
    "        mix = []\n",
    "        for i in arr:\n",
    "            if self.valid_str(i):\n",
    "                continue\n",
    "            for j in mix:\n",
    "                if self.valid_str(i + j):\n",
    "                    continue\n",
    "                else:\n",
    "                    mix.append(i + j)\n",
    "            mix.append(i)\n",
    "        return max([len(i) for i in mix]) if mix else 0\n",
    "\n",
    "    def valid_str(self, string):\n",
    "        return not (len(string) == len(set(string)))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def isCF(s):\n",
    "            return len(set(s)) == len(s)\n",
    "        dp = []\n",
    "        max_len = 0\n",
    "        for s in arr:\n",
    "            if not isCF(s):\n",
    "                continue\n",
    "            for s_ in dp:\n",
    "                if isCF(s_+s):\n",
    "                    dp.append(s_+s)\n",
    "                    max_len = max(max_len,len(s_+s))\n",
    "            max_len = max(max_len,len(s))\n",
    "            dp.append(s)\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def isCF(s):\n",
    "            return len(set(s)) == len(s)\n",
    "        dp = []\n",
    "        for s in arr:\n",
    "            if not isCF(s):\n",
    "                continue\n",
    "            for s_ in dp:\n",
    "                if isCF(s_+s):\n",
    "                    dp.append(s_+s)\n",
    "            dp.append(s)\n",
    "        return len(max(dp,key = len)) if dp else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        \n",
    "        # Helper function to check if a string has all unique characters\n",
    "        def validStr(string):\n",
    "            return len(set(string)) == len(string)\n",
    "        \n",
    "        # Initialize an empty list to store valid concatenated strings\n",
    "        dp = []\n",
    "        \n",
    "        # Iterate through each string in the input list 'arr'\n",
    "        for s in arr:\n",
    "            # If the string does not have unique characters, skip it\n",
    "            if not validStr(s):\n",
    "                continue\n",
    "            # Iterate through all currently stored strings in 'dp'\n",
    "            for s_ in dp:\n",
    "                # If concatenation of stored string 's_' and current string 's' has unique characters, add to 'dp'\n",
    "                if validStr(s_ + s):\n",
    "                    dp.append(s_ + s)\n",
    "            # Append the current string 's' to 'dp' \n",
    "            dp.append(s)\n",
    "        \n",
    "        # Return the length of the longest string in 'dp' if 'dp' is not empty, otherwise return 0\n",
    "        return len(max(dp,key=len)) if dp else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        s=[\"\"]\n",
    "        mx=0\n",
    "        for i in arr:\n",
    "            for j in s:\n",
    "                c=Counter(i+j)\n",
    "                if all([c[i]<2 for i in c.keys()]):\n",
    "                    s.append(i+j)\n",
    "                    mx=max(mx,len(i+j))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def validStr(string):\n",
    "            return len(set(string)) == len(string)\n",
    "        \n",
    "        dp = []\n",
    "        for s in arr:\n",
    "            if not validStr(s):\n",
    "                continue\n",
    "            for s_ in list(dp):\n",
    "                if validStr(s_ + s):\n",
    "                    dp.append(s_ + s)\n",
    "            dp.append(s)\n",
    "        return len(max(dp, key = len)) if dp else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def valid_str(s: str) -> bool:\n",
    "            return len(set(s)) == len(s)\n",
    "\n",
    "        dp = []\n",
    "        for s in arr:\n",
    "            if not valid_str(s): \n",
    "                continue\n",
    "            \n",
    "            for s_ in list(dp):\n",
    "                if valid_str(s_ + s):\n",
    "                    dp.append(s_ + s)\n",
    "            \n",
    "            dp.append(s)\n",
    "        return len(max(dp, key=len)) if dp else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        collect = ['']\n",
    "        ans = 0\n",
    "        for s in arr:\n",
    "            add = []\n",
    "            for c in collect:\n",
    "                t = c+s\n",
    "                if len(t) == len(set(t)):\n",
    "                    add.append(t)\n",
    "                    ans = max(len(t), ans)\n",
    "            collect.extend(add)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        s = ['']\n",
    "        max_len = 0\n",
    "\n",
    "        for i in arr:\n",
    "            if len(s) != len(set(s)):\n",
    "                continue\n",
    "            new = []\n",
    "            for comb in s:\n",
    "                new_s = comb + i\n",
    "                if len(new_s) == len(set(new_s)):\n",
    "                    new.append(new_s)\n",
    "                    max_len = max(max_len, len(new_s))\n",
    "            s.extend(new)\n",
    "        return max_len \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        wordLen = {0: 0}\n",
    "        for i in arr:\n",
    "            flag = 0\n",
    "            isUnique = True\n",
    "            for ch in i:\n",
    "                if 1 << (ord(ch) - ord(\"a\")) & flag:\n",
    "                    isUnique = False\n",
    "                    break\n",
    "                else:\n",
    "                    flag |= 1 << (ord(ch) - ord(\"a\"))\n",
    "\n",
    "            if isUnique:\n",
    "                ans = max(ans, len(i))\n",
    "                for j in list(wordLen.keys()):\n",
    "                    if flag ^ j == flag | j:\n",
    "                        wordLen[flag ^ j] = wordLen[j] + len(i)\n",
    "\n",
    "        return max(wordLen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        ans = 0\n",
    "        wordLen = {0: 0}\n",
    "        for i in arr:\n",
    "            flag = 0\n",
    "            isUnique = True\n",
    "            for ch in i:\n",
    "                if 1 << (ord(ch) - ord(\"a\")) & flag:\n",
    "                    isUnique = False\n",
    "                    break\n",
    "                else:\n",
    "                    flag |= 1 << (ord(ch) - ord(\"a\"))\n",
    "\n",
    "            if isUnique:\n",
    "                ans = max(ans, len(i))\n",
    "                for j in list(wordLen.keys()):\n",
    "                    if flag ^ j == flag | j:\n",
    "                        wordLen[flag ^ j] = wordLen[j] + len(i)\n",
    "\n",
    "        return max(wordLen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        collect = ['']\n",
    "        ans = 0\n",
    "        for s in arr:\n",
    "            add = []\n",
    "            for c in collect:\n",
    "                print(c)\n",
    "                t = c+s\n",
    "                if len(t)==len(set(t)):\n",
    "                    add.append(t)\n",
    "                    ans=max(len(t),ans)\n",
    "            collect.extend(add)\n",
    "            print(collect)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        s={0}\n",
    "        for word in arr:\n",
    "            m=0\n",
    "            for w in word:\n",
    "                bitw=1<<(ord(w)-ord('a'))\n",
    "                if bitw&m: \n",
    "                    m=-1\n",
    "                    break\n",
    "                m|=bitw\n",
    "            if m==-1: continue\n",
    "            subs=set()\n",
    "            for x in s:\n",
    "                if x&m==0: subs.add(x|m)\n",
    "            s|=subs\n",
    "        return max([x.bit_count() for x in s])\n",
    "\n",
    "\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def preprocess(s):\n",
    "            ans = 0\n",
    "            for c in s:\n",
    "                if ans & (1 << (ord(c) - ord('a'))):\n",
    "                    return 0\n",
    "                ans |= 1 << (ord(c) - ord('a'))\n",
    "            return ans\n",
    "        def count(n):\n",
    "            ans = 0\n",
    "            while n:\n",
    "                n &= (n - 1)\n",
    "                ans += 1\n",
    "            return ans\n",
    "        \n",
    "        processed = [preprocess(s) for s in arr] \n",
    "        \n",
    "        combine = [0]\n",
    "        check = set(combine)\n",
    "        for i in processed:\n",
    "            for j in combine:\n",
    "                if i & j or i | j in check:\n",
    "                    continue\n",
    "                combine.append(i | j)\n",
    "                check.add(i | j)\n",
    "\n",
    "        ans = 0\n",
    "        for i in list(combine):\n",
    "            ans = max(ans, count(i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        mask = list()\n",
    "        ret = 0\n",
    "        for word in arr:\n",
    "            bits = 0\n",
    "            i = 0\n",
    "            while i < len(word):\n",
    "                b = 0x1<<(ord(word[i])-97)\n",
    "                if bits & b:\n",
    "                    break\n",
    "                bits |= b\n",
    "                i += 1\n",
    "            if i == len(word):\n",
    "                mask.append(bits)\n",
    "\n",
    "        q = {0}\n",
    "        for bits in mask:\n",
    "            new_q = {x | bits for x in q if x & bits == 0}\n",
    "            q |= new_q\n",
    "            \n",
    "        for bits in q:\n",
    "            length = 0\n",
    "            while bits:\n",
    "                length += 0x1&bits\n",
    "                bits >>= 1\n",
    "            ret = max(ret, length)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # lenarr = len(arr)\n",
    "        # if lenarr == 1:\n",
    "        #     return len(arr[0])\n",
    "        # # (arr, arr)\n",
    "        # lookup = [[0]*lenarr for _ in range(lenarr)]\n",
    "        # for i in range(lenarr):\n",
    "        #     lookup[0][i] = len(arr[i])\n",
    "        \n",
    "        # for i in range(1, lenarr+1):\n",
    "        #     for j in range(i, lenarr):\n",
    "        \n",
    "        base_words = set([0])\n",
    "        add_set = set([0])\n",
    "        max_length = 0\n",
    "        \n",
    "        for word in arr:\n",
    "            add_set.add(self.word2int(word))\n",
    "            base_words.add(self.word2int(word))\n",
    "        base_words.remove(0)\n",
    "        \n",
    "        while len(add_set):\n",
    "            temp_add_set = add_set.copy()\n",
    "            add_set.clear()\n",
    "            for baseword in base_words:\n",
    "                for checkword in temp_add_set:\n",
    "                    if baseword & checkword == 0:\n",
    "                        res = baseword | checkword\n",
    "                        add_set.add(res)\n",
    "                        max_length = max(max_length, bin(res).count('1'))\n",
    "        \n",
    "        return max_length\n",
    "    \n",
    "    def word2int(self, word):\n",
    "        toint = 0\n",
    "        for c in word:\n",
    "            toint_old = toint\n",
    "            toint = toint | 2 ** (ord(c)-ord('a'))\n",
    "            if toint == toint_old:\n",
    "                return 0\n",
    "        return toint\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        \n",
    "        # Helper function to check if a string has all unique characters\n",
    "        def validStr(string):\n",
    "            return len(set(string)) == len(string)\n",
    "        \n",
    "        # Initialize an empty list to store valid concatenated strings\n",
    "        dp = []\n",
    "        \n",
    "        # Iterate through each string in the input list 'arr'\n",
    "        for s in arr:\n",
    "            # If the string does not have unique characters, skip it\n",
    "            if not validStr(s):\n",
    "                continue\n",
    "            # Iterate through all currently stored strings in 'dp'\n",
    "            for s_ in dp:\n",
    "                # If concatenation of stored string 's_' and current string 's' has unique characters, add to 'dp'\n",
    "                if validStr(s_ + s):\n",
    "                    dp.append(s_ + s)\n",
    "            # Append the current string 's' to 'dp' \n",
    "            dp.append(s)\n",
    "            # Debugging print statement (probably can be removed in final version)\n",
    "            print(dp)\n",
    "        \n",
    "        # Return the length of the longest string in 'dp' if 'dp' is not empty, otherwise return 0\n",
    "        return len(max(dp,key=len)) if dp else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "\n",
    "        def check(n,s):\n",
    "            d = 0\n",
    "            vaild = True\n",
    "            r = True\n",
    "            for i in s:\n",
    "                a = 1<<ord(i)-ord('a')\n",
    "                if a&d==a:\n",
    "                    vaild = False\n",
    "                d|= a\n",
    "                if a&n==a:\n",
    "                    r = False\n",
    "            return r,d,vaild\n",
    "        k = 0\n",
    "        dp = []\n",
    "        for s in arr:\n",
    "            used = False\n",
    "            \n",
    "            for j in range(len(dp)):\n",
    "                f,i,vaild = check(dp[j][0],s)\n",
    "                if f and vaild:\n",
    "                    dp.append([dp[j][0]|i,dp[j][1]+len(s)])\n",
    "            f,i,vaild = check(0,s)\n",
    "            if f and vaild:\n",
    "                dp.append([i,len(s)])\n",
    "        if not dp:\n",
    "            return 0\n",
    "        return max(dp,key = lambda i:i[1])[1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        bit_arr = []\n",
    "        for st in arr:\n",
    "            num = 0\n",
    "            for ch in st:\n",
    "                num = num | (1 << (ord(ch) - 97))\n",
    "            bit_arr.append(num)\n",
    "\n",
    "        prefix_arr = [(0, 0)]\n",
    "        for i, num in enumerate(bit_arr):\n",
    "            if '{:032b}'.format(num).count('1') != len(arr[i]): continue\n",
    "            l = len(prefix_arr)\n",
    "            for j in range(l):\n",
    "                x, l = prefix_arr[j]\n",
    "                if num & x == 0:\n",
    "                    prefix_arr.append((num | x, l + len(arr[i])))\n",
    "        prefix_arr.sort(key = lambda x: x[1], reverse = True)\n",
    "        return prefix_arr[0][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def get_key(str):\n",
    "            \"\"\" 用26位int统计字符串词频 \"\"\"\n",
    "            key = 0\n",
    "            for c in str:\n",
    "                if key >> (ord(c)-ord('a')) & 1:\n",
    "                    return 0\n",
    "                key |= 1 << (ord(c)-ord('a'))\n",
    "            return key\n",
    "\n",
    "        # d 用来记录出现过的词频组合\n",
    "        # d = defaultdict(int)\n",
    "        d = {0:0}\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            key = get_key(arr[i])\n",
    "            if not key:\n",
    "                continue\n",
    "            # 遍历之前出现过的词频组合, 若与当前不冲突, 新增该词频组合\n",
    "            new = []\n",
    "            for k_old, v in d.items():\n",
    "                if any((key & k_old) & (1<<i) for i in range(26)):\n",
    "                    pass\n",
    "                else:\n",
    "                   new.append( (key | k_old, len(arr[i]) + v) ) \n",
    "                   ans = max(ans, len(arr[i]) + v)\n",
    "            d.update(new)\n",
    "        # print(d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "\n",
    "        #将其串联所获得的字符串，其中每个字符只出现一次\n",
    "\n",
    "        #要保证其中每个字符只出现一次\n",
    "        #26个字符出现与不出现，一共是1<<26种情况。这样利用背包的话，就需要遍历所有字符出现的情况。\n",
    "        # 而arr的所有组合一共才是1<<16种情况\n",
    "        # 这个拼接实际和拼接顺序没有关系\n",
    "        # \n",
    "\n",
    "        def check(string):\n",
    "            stringSet=set(string)\n",
    "            if len(stringSet)!=len(string):\n",
    "                return 0\n",
    "            val=0\n",
    "            for char in string:\n",
    "                val|=1<<ord(char)-97\n",
    "            \n",
    "            return val\n",
    "\n",
    "        cache=collections.defaultdict(int)\n",
    "        cache[0]=0\n",
    "        for string in arr:\n",
    "            val=check(string)\n",
    "            if val==0:\n",
    "                continue\n",
    "            length=len(string)\n",
    "\n",
    "            for key in set(cache.keys()):      #在遍历中修改cache，但新添加的必然和Val重复了\n",
    "                if key&val==0:  #此时说明没有交集。如果原本的key不同，那么交集之后的结果也将不同。但可能会与现有的key冲突\n",
    "                    res=key|val\n",
    "                    cache[res]=max(cache[res],cache[key]+length)\n",
    "        \n",
    "        return max(cache.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "\n",
    "        #将其串联所获得的字符串，其中每个字符只出现一次\n",
    "\n",
    "        #要保证其中每个字符只出现一次\n",
    "        #26个字符出现与不出现，一共是1<<26种情况。这样利用背包的话，就需要遍历所有字符出现的情况。\n",
    "        # 而arr的所有组合一共才是1<<16种情况\n",
    "        # 这个拼接实际和拼接顺序没有关系\n",
    "        # \n",
    "\n",
    "        def check(string):\n",
    "            stringSet=set(string)\n",
    "            if len(stringSet)!=len(string):\n",
    "                return 0\n",
    "            val=0\n",
    "            for char in string:\n",
    "                val|=1<<ord(char)-97\n",
    "            \n",
    "            return val\n",
    "\n",
    "        cache=collections.defaultdict(int)\n",
    "        cache[0]=0\n",
    "        for string in arr:      #本质上仍然是背包，但我们只需要考虑实际可能取的值，而不用遍历1<<26种结果\n",
    "            val=check(string)\n",
    "            if val==0:\n",
    "                continue\n",
    "            length=len(string)\n",
    "\n",
    "            for key in set(cache.keys()):      #在遍历中修改cache，但新添加的必然和Val重复了\n",
    "                if key&val==0:  #此时说明没有交集。如果原本的key不同，那么交集之后的结果也将不同。但可能会与现有的key冲突\n",
    "                    res=key|val\n",
    "                    cache[res]=max(cache[res],cache[key]+length)\n",
    "        \n",
    "        return max(cache.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        als = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        dic = {}\n",
    "        for i,ch in enumerate(als):\n",
    "            dic[ch] = 1<<i\n",
    "        \n",
    "        def getNum(str_):\n",
    "            rel = 0\n",
    "            for ch in str_:\n",
    "                rel |= dic[ch]\n",
    "            return rel\n",
    "        \n",
    "        dic1 = {0:0}\n",
    "        for str_ in arr:\n",
    "            if(len(str_)!=len(set(str_))):\n",
    "                continue\n",
    "            temp = {}\n",
    "            strNum = getNum(str_)\n",
    "            for k,v in dic1.items():\n",
    "                if strNum&k == 0:\n",
    "                    temp[strNum|k] = len(str_)+v\n",
    "            for k,v in temp.items():\n",
    "                dic1[k] = v\n",
    "        return max(dic1.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        dp={''}\n",
    "        for a in arr:\n",
    "            aset=set(a)\n",
    "            if len(a)>len(aset):\n",
    "                continue\n",
    "            newdp=dp.copy()\n",
    "            for seq in dp:\n",
    "                if not (aset & set(seq)):\n",
    "                    newdp.add(seq+a)\n",
    "            dp=newdp\n",
    "        return max(len(seq) for seq in dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def get_code(x):\n",
    "            code=0\n",
    "            for c in x:\n",
    "                code|=2**(ord(c)-97)\n",
    "            return code\n",
    "\n",
    "        nums={get_code(x) for x in arr if len(x)==len(set(x))}\n",
    "        st=set()\n",
    "        for n in nums:\n",
    "            st2={n}\n",
    "            for m in st:\n",
    "                if n&m==0:\n",
    "                    st2.add(m|n)\n",
    "            st=st|st2\n",
    "        if not st:\n",
    "            return 0\n",
    "        return max(bin(x).count('1') for x  in st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        f[k]=f[k-1] s[k]\n",
    "        \"\"\"\n",
    "        all_max_str = [\"\"]\n",
    "        #max_str = []\n",
    "        for an_str in arr:\n",
    "            if len(set(an_str)) < len(an_str):\n",
    "                continue\n",
    "            tmp_all_max_str=[]\n",
    "            for j, an_all_max_str in enumerate(all_max_str):\n",
    "                \"\"\"\n",
    "                add_flag = 1\n",
    "                for i,an_str_InMax in enumerate(max_str):\n",
    "                    if len(set(an_str) & set(an_str_InMax)) > 0:\n",
    "                        if len(an_str) > len(an_str_InMax):\n",
    "                            max_str[i]=\"\"\n",
    "                        else:\n",
    "                            add_flag=0\n",
    "                        break\n",
    "                if add_flag:\n",
    "                    max_str.append(an_str)\n",
    "                \"\"\"\n",
    "                tmp_max_str = an_all_max_str+an_str\n",
    "                \n",
    "                if len(set(tmp_max_str)) < len(tmp_max_str):\n",
    "                    continue\n",
    "                tmp_all_max_str.append(tmp_max_str)\n",
    "            all_max_str += tmp_all_max_str\n",
    "\n",
    "        #print(all_max_str)\n",
    "        if len(all_max_str) > 0:\n",
    "            all_max_str.sort(key=lambda x:-len(x))\n",
    "            return len(all_max_str[0])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def to_binary(w):\n",
    "            v = 0\n",
    "            for c in w:\n",
    "                bit = 1 << (ord(c) - ord('a'))\n",
    "                if v & bit > 0:\n",
    "                    return -1\n",
    "                v += bit \n",
    "            return v \n",
    "\n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for j in range(i, n):\n",
    "                if arr_bin[j] > 0 and state & arr_bin[j] == 0:\n",
    "                    ans = max(ans, len(arr[j]) + dfs(j+1, state + arr_bin[j]))\n",
    "            return ans\n",
    "\n",
    "        n = len(arr)\n",
    "        arr_bin = [to_binary(word) for word in arr]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def vali_str(string):\n",
    "            return len(string) == len(set(string))\n",
    "\n",
    "        if len(arr) == 1 and vali_str(arr[0]):\n",
    "            return len(arr[0])\n",
    "        dp = [\"\"]\n",
    "        for string in arr:\n",
    "            if not vali_str(string):\n",
    "                continue\n",
    "            for s_dp in dp:\n",
    "                new_s = string+s_dp\n",
    "                if vali_str(new_s):\n",
    "                    dp.append(new_s)\n",
    "            dp.append(string)\n",
    "        \n",
    "        return len(max(dp, key=len))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def maxLength(self, arr: List[str]) -> int:\n",
    "            res_list = [[]]\n",
    "            for a in arr:\n",
    "                if len(set(a)) != len(a):\n",
    "                    continue\n",
    "                for i in range(len(res_list)):\n",
    "                    if not set(''.join(res_list[i])) & set(a):\n",
    "                        res_list.append(res_list[i] + [a])\n",
    "            return max([len(''.join(i)) for i in res_list])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # Draw a tree, solve get ans, get all possible concatenated strings\n",
    "        res = []\n",
    "        path = []\n",
    "        \n",
    "        def dfs(arr, path, res):\n",
    "            if not arr: # arr is empty\n",
    "                res.append(path)\n",
    "                return\n",
    "\n",
    "            # trim, if we can add arr[0] to current path?\n",
    "            new_path = ''.join(path + [arr[0]])\n",
    "            if len(set(list(new_path))) == len(new_path):\n",
    "                dfs(arr[1:], path+[arr[0]], res)\n",
    "            dfs(arr[1:], path, res)\n",
    "\n",
    "        dfs(arr, path, res)\n",
    "        ans = [len(''.join(item)) for item in res]\n",
    "        #print(ans)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        count=0\n",
    "        cur =[[]]\n",
    "        for i in arr:\n",
    "            cur+=[[i]+num for num in cur]\n",
    "        for i in cur:\n",
    "            s=\"\".join(i)\n",
    "            a=[]\n",
    "            for j in s:\n",
    "                a.append(j)\n",
    "            if len(a)==len(set(a)):\n",
    "                count=max(count,len(a))\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def judge(s):\n",
    "            if len(s) == len(set(s)):\n",
    "                return True\n",
    "            return False\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        cur = [[]]\n",
    "        for c in arr:\n",
    "            if judge(c):\n",
    "                cur += [[c] + num for num in cur if judge([c] + num)]\n",
    "        for c in cur:\n",
    "            s = ''.join(c)\n",
    "            if len(list(s)) == len(set(list(s))):\n",
    "                cnt = max(cnt, len(list(s)))\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxLength(self, arr):\n",
    "        count=0;\n",
    "        res=\"\";\n",
    "        cur =[[]];\n",
    "        for i in arr:\n",
    "            cur+=[[i]+num for num in cur];\n",
    "        #print(cur);\n",
    "        for i in cur:\n",
    "            s=\"\".join(i);\n",
    "            a=[];\n",
    "            for j in s:\n",
    "                a.append(j);\n",
    "            if len(a)==len(set(a)):\n",
    "               # print(a);\n",
    "                count=max(count,len(a));\n",
    "        return count;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def geneMask(s):\n",
    "            mask = 0\n",
    "            for ch in s:\n",
    "                mask |= (1<<(ord(ch)-ord('a')))\n",
    "            return mask\n",
    "        \n",
    "        def dfs(curr,idx):\n",
    "            nonlocal maxLen\n",
    "            maxLen = max(maxLen,len(curr))\n",
    "            mask = geneMask(curr)\n",
    "            for i in range(idx,len(arr)):\n",
    "                if mask & geneMask(arr[i]) == 0:\n",
    "                    dfs(curr+arr[i],i+1)\n",
    "\n",
    "        arr = [ x  for x in arr if max((collections.Counter(x)).values()) == 1] \n",
    "        maxLen = 0    \n",
    "        dfs(\"\",0)\n",
    "        return maxLen  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        trace = []\n",
    "        ans = []\n",
    "        def is_unique(str1):\n",
    "            return True if len(str1)==len(set(str1)) else False\n",
    "        \n",
    "        def traceback(startindex):\n",
    "            if startindex > len(arr):\n",
    "                return\n",
    "            else:\n",
    "                ans.append(trace[:])\n",
    "            for i in range(startindex,len(arr)):\n",
    "                if not is_unique(\"\".join(trace)+arr[i]):\n",
    "                    continue                \n",
    "                trace.append(arr[i])\n",
    "                traceback(i+1)\n",
    "                trace.pop()\n",
    "        traceback(0)\n",
    "        return max([len(\"\".join(i).strip()) for i in ans])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        result = []\n",
    "        self.helper(result, 0, arr, [])\n",
    "        ans = 0\n",
    "        for sub in result:\n",
    "            if len(set(''.join(sub))) == len(''.join(sub)):\n",
    "                ans = max(ans, len(''.join(sub)))\n",
    "        return ans\n",
    "\n",
    "    def helper(self, result, index, arr, subset):\n",
    "        result.append(subset[:])\n",
    "        for i in range(index, len(arr)):\n",
    "            subset.append(arr[i])\n",
    "            self.helper(result, i+1, arr, subset)\n",
    "            subset.pop()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # if arr == '':\n",
    "        #     return len(res)\n",
    "        # else:\n",
    "        #     arr = sorted(arr,key = lambda x: len(x),reverse = True)\n",
    "        #     res = ''\n",
    "        #     for s in arr:\n",
    "        #         if len(res+s) == len(set(res+s)):\n",
    "        #             res += s\n",
    "        #     return len(res)\n",
    "\n",
    "        # collect = ['']\n",
    "        # ans = 0\n",
    "        # for s in arr:\n",
    "        #     add = []\n",
    "        #     for c in collect:\n",
    "        #         t = c+s\n",
    "        #         if len(t)==len(set(t)):\n",
    "        #             add.append(t)\n",
    "        #             ans = max(len(t),ans)\n",
    "        #     collect.extend(add)\n",
    "        # return ans\n",
    "\n",
    "        collect = ['']\n",
    "        res = 0\n",
    "        for s in arr:\n",
    "            if len(s) == len(set(s)):\n",
    "                collect.append(s)\n",
    "            for c in collect:\n",
    "                if len(s+c) == len(set(s+c)):\n",
    "                    collect.append(s+c)\n",
    "                    res = max(len(s+c),res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import add\n",
    "from functools import reduce\n",
    "from itertools import chain\n",
    "\n",
    "def toNum(s):\n",
    "    num = 0\n",
    "    for c in s:\n",
    "        sl = ord(c) - ord('a')\n",
    "        if (num >> sl) & 1 == 1: return 0\n",
    "        else: num += 1 << sl\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        acc_set = set([(0, 0)])\n",
    "        for s in arr:\n",
    "            num = 0\n",
    "            for c in s:\n",
    "                sl = ord(c) - ord('a')\n",
    "                if (num >> sl) & 1 == 1:\n",
    "                    num = 0\n",
    "                    break\n",
    "                else:\n",
    "                    num += 1 << sl\n",
    "            if num == 0: continue\n",
    "\n",
    "            slen = len(s)\n",
    "            new_acc = set()\n",
    "            for acc, acc_len in acc_set:\n",
    "                if num & acc == 0:\n",
    "                    new_len = slen + acc_len\n",
    "                    new_acc.add((num | acc, new_len))\n",
    "            acc_set |= new_acc\n",
    "\n",
    "        return max(map(lambda x: x[1], acc_set))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        conflicts = dict()\n",
    "        tmp = []\n",
    "        for s in arr:\n",
    "            illegal = 0\n",
    "            for v in Counter(s).values():\n",
    "                if v > 1:\n",
    "                    illegal = 1\n",
    "                    break\n",
    "            if not illegal:\n",
    "                tmp.append(s)\n",
    "        arr = tmp\n",
    "        \n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            conflicts[i] = set()\n",
    "        for i in range(n-1):\n",
    "            chars_i = set(arr[i])\n",
    "            for j in range(i+1, n):\n",
    "                chars_j = set(arr[j])\n",
    "                if len(chars_i.intersection(chars_j)) > 0:\n",
    "                    conflicts[i].add(j)\n",
    "        max_l = 0\n",
    "        combs = [('', 0, set(), list(range(n)))]\n",
    "        while combs:\n",
    "            tmp = []\n",
    "            for concat_s, length, not_allowed, indice_left in combs:\n",
    "                for i_pos in range(len(indice_left)):\n",
    "                    i = indice_left[i_pos]\n",
    "                    if i not in not_allowed:\n",
    "                        new_concat_s = concat_s + arr[i]\n",
    "                        new_length = length + len(arr[i])\n",
    "                        new_not_allowed = not_allowed.union(conflicts[i])\n",
    "                        new_indice_left = indice_left[(i_pos+1):]\n",
    "                        max_l = max(max_l, new_length)\n",
    "                        tmp.append((new_concat_s, new_length, new_not_allowed, new_indice_left))\n",
    "            combs = tmp\n",
    "        return max_l\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        n = len(arr)\n",
    "        res = ['']\n",
    "        ans = 0\n",
    "        for i, s in enumerate(arr):\n",
    "            res += [ s + subres for subres in res]\n",
    "        for s in res:\n",
    "            if len(s) == len(set(s)):\n",
    "               ans = max(ans, len(s))\n",
    "        return ans \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        dic = {}\n",
    "        alllen = 0\n",
    "        for i in arr:\n",
    "            alllen += len(i)\n",
    "        def dfs(index,nowstr,nowlen,restlen,result):\n",
    "            if (index,nowstr,nowlen,restlen,result) in dic:\n",
    "                return dic[(index,nowstr,nowlen,restlen,result)]\n",
    "            if nowlen + restlen < result:\n",
    "                dic[(index,nowstr,nowlen,restlen,result)] = result\n",
    "                return result\n",
    "            restlen -= len(arr[index])\n",
    "            if len(set(nowstr + arr[index])) < nowlen + len(arr[index]):\n",
    "                if nowlen + restlen < result:\n",
    "                    dic[(index,nowstr,nowlen,restlen,result)] = result\n",
    "                    return result\n",
    "                else:\n",
    "                    if index + 1 == len(arr):\n",
    "                        dic[(index,nowstr,nowlen,restlen,result)] = result\n",
    "                        return result\n",
    "                    else:\n",
    "                        result = dfs(index+1,nowstr,nowlen,restlen,result)\n",
    "                        dic[(index,nowstr,nowlen,restlen,result)] = result\n",
    "                        return result\n",
    "            else:\n",
    "                if index + 1 == len(arr):\n",
    "                    dic[(index,nowstr,nowlen,restlen,result)] = result + len(arr[index])\n",
    "                    return result + len(arr[index])\n",
    "                else:\n",
    "                    result = max(dfs(index+1,nowstr,nowlen,restlen,result),dfs(index+1,nowstr+arr[index],nowlen+len(arr[index]),restlen,result+len(arr[index])))\n",
    "                    dic[(index,nowstr,nowlen,restlen,result)] = result\n",
    "                    return result\n",
    "        result = dfs(0,'',0,alllen,0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # if arr == '':\n",
    "        #     return len(res)\n",
    "        # else:\n",
    "        #     arr = sorted(arr,key = lambda x: len(x),reverse = True)\n",
    "        #     res = ''\n",
    "        #     for s in arr:\n",
    "        #         if len(res+s) == len(set(res+s)):\n",
    "        #             res += s\n",
    "        #     return len(res)\n",
    "\n",
    "        # collect = ['']\n",
    "        # ans = 0\n",
    "        # for s in arr:\n",
    "        #     add = []\n",
    "        #     for c in collect:\n",
    "        #         t = c+s\n",
    "        #         if len(t)==len(set(t)):\n",
    "        #             add.append(t)\n",
    "        #             ans = max(len(t),ans)\n",
    "        #     collect.extend(add)\n",
    "        # return ans\n",
    "\n",
    "        collect = ['']\n",
    "        for s in arr:\n",
    "            if len(s) == len(set(s)):\n",
    "                collect.append(s)\n",
    "            for c in collect:\n",
    "                if len(s+c) == len(set(s+c)):\n",
    "                    collect.append(s+c)\n",
    "        res = max([len(t) for t in collect])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        # if arr == '':\n",
    "        #     return len(res)\n",
    "        # else:\n",
    "        #     arr = sorted(arr,key = lambda x: len(x),reverse = True)\n",
    "        #     res = ''\n",
    "        #     for s in arr:\n",
    "        #         if len(res+s) == len(set(res+s)):\n",
    "        #             res += s\n",
    "        #     return len(res)\n",
    "\n",
    "        # collect = ['']\n",
    "        # ans = 0\n",
    "        # for s in arr:\n",
    "        #     add = []\n",
    "        #     for c in collect:\n",
    "        #         t = c+s\n",
    "        #         if len(t)==len(set(t)):\n",
    "        #             add.append(t)\n",
    "        #             ans = max(len(t),ans)\n",
    "        #     collect.extend(add)\n",
    "        # return ans\n",
    "\n",
    "        collect = ['']\n",
    "        for s in arr:\n",
    "            if len(s) == len(set(s)):\n",
    "                collect.append(s)\n",
    "            for c in collect:\n",
    "                if len(s+c) == len(set(s+c)):\n",
    "                    collect.append(s+c)\n",
    "        res = max([len(t) for t in collect])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:        \n",
    "        dp = dict()\n",
    "        for s in arr:\n",
    "            t = set(s)\n",
    "            if len(t) != len(s):\n",
    "                continue\n",
    "            for key, value in list(dp.items()):\n",
    "                if not set(key) & t:\n",
    "                    dp[tuple(set(key)|t,)] = value + len(t)\n",
    "            dp[tuple(t,)] = len(t)\n",
    "        return max(dp.values()) if dp else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        n = len(arr)\n",
    "        strSet = set()\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            cList = [\"0\" for _ in range(26)]\n",
    "            count = 0\n",
    "            m = len(arr[i])\n",
    "            for j in range(m):\n",
    "                ind = ord(arr[i][j])-ord(\"a\")\n",
    "                if cList[ind]==\"0\":\n",
    "                    cList[ind] = \"1\"\n",
    "                    count += 1\n",
    "                    if j==m-1:\n",
    "                        ans = max(ans,count)\n",
    "                        s = \"\".join(cList)\n",
    "                else:\n",
    "                    s = \"\"\n",
    "                    break\n",
    "            if s == \"\":\n",
    "                continue\n",
    "            addSet = {s}\n",
    "            for ele in strSet:\n",
    "                if int(s,2) & int(ele,2) == 0:\n",
    "                    combi = bin(int(s,2)^int(ele,2))\n",
    "                    count = combi.count(\"1\")\n",
    "                    ans = max(ans,count)\n",
    "                    addSet.add(combi)\n",
    "            strSet = strSet | addSet\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "\n",
    "        ret = []\n",
    "        subset = []\n",
    "        def dfs(i=0):\n",
    "            if i>=len(arr):\n",
    "                ret.append(''.join(subset))\n",
    "                return \n",
    "            \n",
    "            subset.append(arr[i])\n",
    "            dfs(i+1)\n",
    "            subset.pop()\n",
    "            dfs(i+1)\n",
    "\n",
    "        def isValid(s):\n",
    "            s = [x for x in s]\n",
    "            if len(s)==len(set(s)):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        dfs()\n",
    "        ret = [len(x) for x in ret if isValid(x)]\n",
    "        # ret = [len(x) for x in ret]\n",
    "        return max(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxLength(self, arr):\n",
    "\t\tpool = set()\n",
    "\t\tans = 0\n",
    "\t\tfor s in arr:\n",
    "\t\t\tcur = set(s)\n",
    "\t\t\tif len(s) != len(cur):\n",
    "\t\t\t\tcontinue\n",
    "\t\t\tbit = self.calc(cur)\n",
    "\t\t\ttmp = {(bit, len(s))}\n",
    "\t\t\tans = max(ans, len(s))\n",
    "\t\t\tfor p, l in pool:\n",
    "\t\t\t\tif p | bit == p + bit:\n",
    "\t\t\t\t\ttmp.add((p | bit, l + len(s)))\n",
    "\t\t\t\t\tans = max(ans, l + len(s))\n",
    "\t\t\tpool.update(tmp)\n",
    "\t\treturn ans\n",
    "\t\n",
    "\tdef calc(self, pool):\n",
    "\t\tres = 0\n",
    "\t\tfor char in pool:\n",
    "\t\t\tres |= 1 << (ord(char) - 97)\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        res = [0]\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def dfs(s, index):\n",
    "            for i in range(index, n):\n",
    "                s2 = s+arr[i]\n",
    "                if len(s2) == len(set(s2)):\n",
    "                    res[0] = max(res[0], len(s2))\n",
    "                    dfs(s2,i+1)\n",
    "        dfs(\"\", 0)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        bits = []\n",
    "        base = ord('a')\n",
    "        for s in arr:\n",
    "            bit = 0\n",
    "            flag = True\n",
    "            for c in s:\n",
    "                if bit & (1<<(ord(c)-base)):\n",
    "                    flag = False\n",
    "                    break\n",
    "                bit |= 1<<(ord(c)-base)\n",
    "            if flag:\n",
    "                bits.append(bit)\n",
    "        n = len(bits)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(smask, bitmask):\n",
    "            ret = -1\n",
    "            for i in range(n):\n",
    "                if smask & (1<<i):\n",
    "                    continue\n",
    "                if bitmask & bits[i] != 0:\n",
    "                    continue\n",
    "                ret = max(ret, dfs(smask|(1<<i), bitmask | bits[i]))\n",
    "            if ret == -1:\n",
    "                return str(bin(bitmask)).count('1')\n",
    "            return ret\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    \n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        def noDuplication(word) -> bool:\n",
    "            return len(set(word)) == len(word)\n",
    "        \n",
    "        def isValid(word, path) -> bool:\n",
    "            for c in word:\n",
    "                if c in path:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        copy = []\n",
    "        for word in arr:\n",
    "            if noDuplication(word):\n",
    "                copy.append(word)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(start, path):\n",
    "            for i in range(start, len(copy)):\n",
    "                word = copy[i]\n",
    "                if isValid(word, path):\n",
    "                    path += word\n",
    "                    self.ans = max(self.ans, len(path))\n",
    "                    dfs(i + 1, path)\n",
    "                    path = path[:-len(word)]  # backtracking\n",
    "        \n",
    "        dfs(0, '')\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        sets = [set(a) for a in arr]\n",
    "        invalid_indices = set()\n",
    "        for i, s in enumerate(sets):\n",
    "            if len(s) < len(arr[i]): invalid_indices.add(i)\n",
    "\n",
    "        @cache\n",
    "        def dfs(start, string):\n",
    "            if start == len(arr): return len(string)\n",
    "            str_set = set(string)\n",
    "            ans = len(string)\n",
    "            for i in range(start, len(arr)):\n",
    "                if i in invalid_indices or sets[i].intersection(str_set): continue\n",
    "                ans = max(ans, dfs(i+1, string + arr[i]))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, arr: List[str]) -> int:\n",
    "        a = []\n",
    "        for s in arr:\n",
    "            if len(s) == len(set(s)):\n",
    "                a.append(functools.reduce(lambda x,y: x|y, [1 << (ord(c) - ord('a')) for c in s]))\n",
    "        \n",
    "        n = len(a)\n",
    "        @cache\n",
    "        def f(x, mask):\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if x & (1 << i) or mask & a[i]:\n",
    "                    continue\n",
    "                ans = max(ans, a[i].bit_count() + f(x | (1 << i), mask | a[i]))\n",
    "            return ans\n",
    "\n",
    "        return f(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
